package com.base.leetcode;

/**
 * @Author: hdhao
 * @Create: 2023/3/30 - 22:57
 * @Version: v1.0
 */
//检测环的入口
public class Leetcode142 {

    //判断带环的链表中环的入口
    public ListNode detectCycle(ListNode head){
        //兔子指针(每次走两步)
        ListNode h = head;
        //乌龟指针(每次走一步)
        ListNode t = head;
        while (h!=null && h.next!=null){
            t = t.next;
            h = h.next.next;
            //兔子和龟相遇
            if (t == h){
                //进入第二阶段
                t = head;
                while (true){
                    if (t == h){
                        return t;
                    }
                    t = t.next;
                    h = h.next;
                }
            }
        }
        return null;
    }
}
